package com.njupt.Tree;

import java.nio.file.Path;
import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/2 10:18
 * @Description: 113. 路径总和 II
 * @Version: 1.0
 */


public class PathSum {

    /**
     * 递归 + 回溯算法
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> results = new ArrayList<>();
        if(root == null) return results;
        List<Integer> integers = new ArrayList<>();
        calTargetPath(root,results,integers,targetSum);
        return results;
    }

    private void calTargetPath(TreeNode root, List<List<Integer>> results,List<Integer> integers, int targetSum) {
        integers.add(root.val);
        if(root.left == null && root.right == null){
            int sum = 0;
            for (int i = 0; i < integers.size(); i++) {
                sum += integers.get(i);
            }
            if(sum == targetSum){
                results.add(new ArrayList<>(integers));
            }
            return;
        }
        if(root.left != null){
            calTargetPath(root.left,results,integers,targetSum);
            integers.remove(integers.size()-1);
        }
        if(root.right != null){
            calTargetPath(root.right,results,integers,targetSum);
            integers.remove(integers.size()-1);
        }

    }


    /**
     * 后续遍历非递归算法
     * @param root
     * @param targetSum
     * @return
     */
    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        List<List<Integer>> results = new ArrayList<>();
        if(root == null) return results;

        Deque<TreeNode> treeStack = new LinkedList<>();
        Deque<Boolean> flagStack = new LinkedList<>();
        TreeNode cur = root;
        Boolean flag = false;
        while(cur != null || !treeStack.isEmpty()){
            if(cur != null){

                treeStack.push(cur);
                flagStack.push(false);
                cur = cur.left;
            }else {
                cur = treeStack.pop();
                flag = flagStack.pop();
                if(flag == false){
                    treeStack.push(cur);
                    flagStack.push(true);
                    cur = cur.right;
                }else {
                    //访问节结点
                    if(cur.left == null && cur.right == null){
                        int sum = cur.val;
                        Iterator<TreeNode> iterator = treeStack.iterator();
                        while(iterator.hasNext()){
                            sum +=iterator.next().val;
                        }
                        if(sum == targetSum){
                            Iterator<TreeNode> iterator1 = treeStack.iterator();
                            List<Integer> integers = new ArrayList<>();
                            integers.add(cur.val);
                            while(iterator1.hasNext()){
                                integers.add(iterator1.next().val);
                            }
                            Collections.reverse(integers);
                            results.add(integers);
                        }
                    }
                    cur = null;
                }
            }
        }
        return results;

    }

    public static void main(String[] args) {

        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);

        PathSum test = new PathSum();
        List<List<Integer>> lists = test.pathSum(root, 22);
        Iterator<List<Integer>> iterator = lists.iterator();
        while(iterator.hasNext()){
            List<Integer> next = iterator.next();
            System.out.println(next);
        }



    }
}
